0% completed
Problem Statement
Given the roots of two binary trees, root and subRoot, return true if subRoot is a subtree of root. Otherwise, return false.
A subtree of a binary tree is a part of the tree that includes a node and all of its descendants. The tree tree could also be considered as a subtree of itself.
Examples
Example 1
- Input: root =
[3, 6, 5, 1, 4], subRoot =[6, 1, 4]
- Expected Output:
true - Explanation: The subtree starting at node 6 in
roothas the same structure and values assubRoot.
Example 2
- Input: root =
[3, 4, 5, null, 2, null, 1], subRoot =[4, null, 2]
- Expected Output:
true - Explanation: The subtree rooted at node 4 in
rootmatches the structure and values ofsubRoot.
Example 3
- Input: root =
[3, 4, 5, 1, 2, null, null, 0], subRoot =[4, 1, 2]
- Expected Output:
false - Explanation: While node 4 exists in
root, its subtree structure is different because of the extra node0.
Constraints:
- The number of nodes in the root tree is in the range [1, 2000].
- The number of nodes in the subRoot tree is in the range [1, 1000].
- -104 <= root.val <= 104
- -104 <= subRoot.val <= 104
Solution
In this problem, the goal is to check whether subRoot is a subtree of root. We use a recursive algorithm that traverses the entire root tree, comparing each node's subtree with subRoot. The algorithm checks if the trees rooted at the current node of root and subRoot are identical. If they are, the function returns true. If not, the algorithm recursively checks the left and right subtrees of root. This method ensures that all possible subtrees of root are examined to see if they match subRoot.
We use a helper function to compare two trees. It determines if both trees have the same structure and node values. It recursively checks the left and right children of both trees. The algorithm relies on this helper function to determine if two trees are identical. If at any point the current subtree of root matches subRoot, we return true, otherwise, we continue searching the rest of root.
Step-by-step Algorithm
-
Base Case: Check if
subRootisnull:- If
subRootisnull, returntrue. This is because an empty tree is always a subtree of any tree.
- If
-
Base Case: Check if
rootisnull:- If
rootisnullandsubRootis notnull, returnfalse. This is because a non-empty tree cannot be a subtree of an empty tree.
- If
-
Check if the current subtree rooted at
rootmatchessubRoot:- Call the helper function
isSameTree(root, subRoot)to check if the subtree rooted at the current node ofrootis identical tosubRoot. This comparison involves:- If both nodes are
null, returntrue(both are identical). - If one of the nodes is
nulland the other is not, returnfalse(they cannot be identical). - If the values of the current nodes are different, return
false(the trees cannot be identical). - If the values of the current nodes are the same, recursively check if the left and right subtrees of both trees are identical by calling
isSameTreeon their respective left and right children.
- If both nodes are
- Call the helper function
-
Recursively check the left and right subtrees of
root:- If the current subtree rooted at
rootdoes not matchsubRoot, recursively callisSubtree(root.left, subRoot)andisSubtree(root.right, subRoot)to check the left and right subtrees ofroot.
- If the current subtree rooted at
-
Return the result:
- If at any point the trees match, return
true. If no subtree matchessubRoot, returnfalse.
- If at any point the trees match, return
Algorithm Walkthrough
Input: root = [3, 6, 5, 1, 4], subRoot = [6, 1, 4]):
-
Starting at the root node of
root(node 3):- Current Node in
root: 3 - Comparing with
subRoot(node 6):- Node values are different (
3 != 6), so we move forward to check the left and right subtrees ofroot.
- Node values are different (
- Current Node in
-
Checking the left subtree of
root:-
Current Node in
root: 6 (left child of node 3) -
Comparing with
subRoot(node 6):- Node values are the same (
6 == 6), so we now check the left and right subtrees of this node to see if they also match.
- Node values are the same (
-
Comparing the left subtrees of node 6 in
rootandsubRoot:- Left child of node 6 in
root: 1 - Left child of node 6 in
subRoot: 1 - Comparison:
- Node values are the same (
1 == 1), and both nodes have no further children (both left and right children arenull).
- Node values are the same (
- Result: The left subtrees are identical.
- Left child of node 6 in
-
Comparing the right subtrees of node 6 in
rootandsubRoot:- Right child of node 6 in
root: 4 - Right child of node 6 in
subRoot: 4 - Comparison:
- Node values are the same (
4 == 4), and both nodes have no further children (both left and right children arenull).
- Node values are the same (
- Result: The right subtrees are identical.
- Right child of node 6 in
-
-
Conclusion
- Since both the left and right subtrees of node 6 in
rootmatch those insubRoot, the trees are identical. - The helper function
isSameTree(root, subRoot)returnstrue.
- Since both the left and right subtrees of node 6 in
-
Final Step
- The
isSubtreefunction also returnstrue, confirming thatsubRootis indeed a subtree ofroot.
- The
Code
Complexity Analysis
Time Complexity
- In the worst case, for every node in the
roottree, we call theisSameTree()method to compare it with thesubRoot. This results in a time complexity of, where: nis the number of nodes in theroottree.mis the number of nodes in thesubRoottree.
- The
isSameTree()method itself takestime as it compares all nodes in subRootwith the corresponding nodes inroot. - Therefore, the overall time complexity is
.
Space Complexity
- The space complexity is determined by the depth of the recursion, which depends on the height of the trees.
- In the worst case (for a completely unbalanced tree), the height of the tree could be
for rootandfor subRoot. - Thus, the space complexity is
, where h1andh2are the heights of therootandsubRoottrees, respectively. In the worst case, this could beif both trees are skewed.
An Alternate Approach Using Tree Hash
In the first approach, the time complexity was N is the number of nodes in root and M is the number of nodes in subRoot. To optimize this, we use a hashing-based approach.
In this approach, we calculate the hash value for each subtree in root and store it. Then, we calculate the hash for subRoot and compare it with the stored hashes from root. If a match is found, we can immediately conclude that subRoot is a subtree of root. This optimization reduces the comparison time and improves efficiency by leveraging hashing techniques.
The overall approach is efficient because:
- Instead of comparing entire subtrees at each node, we convert subtrees into hashes, reducing the need for full comparisons.
- We use two prime numbers to generate unique hashes, minimizing the chances of collisions and ensuring correctness.
Step-by-step Algorithm
-
Initialize constants and data structures:
- Set two prime constants
MOD_PRIME_1andMOD_PRIME_2for hashing to minimize hash collisions. - Create a list
hashStoreto store the hashes of all subtrees inroot.
- Set two prime constants
-
Define the
calculateHashForSubtreefunction:-
Base Case: If the current node is
null, return a default hash value{3, 7}to handle empty subtrees. Here, you can return any pair of prime numbers. -
Recursively calculate the hashes for the left and right subtrees of the current node by calling
calculateHashForSubtreeon both. -
Hash Calculation For the First Hash of the Pair:
-
Left Shift the Left Subtree Hash: Take the first hash of the left subtree and left shift it by a fixed value (e.g., 5). This gives more weight to the left subtree.
-
Left Shift the Right Subtree Hash: Take the first hash of the right subtree and left shift it by 1 (or another fixed value). This adds the right subtree’s contribution with slightly less weight.
-
Add Node’s Value: Add the shifted values of the left and right subtree hashes to the current node's value. This combines the contributions of the subtrees and the current node.
-
Take MOD_1: Apply
MOD_PRIME_1to the result to avoid overflow and keep the hash value within a manageable range.
-
-
Hash Calculation For the Second Hash of the Pair:
-
Left Shift the Left Subtree Hash: Take the second hash of the left subtree and left shift it by a different fixed value (e.g., 7). This gives a different weight to the left subtree for the second hash.
-
Left Shift the Right Subtree Hash: Take the second hash of the right subtree and left shift it by 1 (or another fixed value). This adds the right subtree’s contribution with a slight weight.
-
Add Node’s Value: Add the shifted values of the left and right subtree hashes to the current node's value to compute the second part of the hash.
-
Take MOD_2: Apply
MOD_PRIME_2to the result to avoid overflow and ensure the second hash value remains within the bounds of the prime.
-
-
-
Hash all subtrees in
root:- Call
calculateHashForSubtree(root, true)to compute and store the hashes of all subtrees inroot.
- Call
-
Hash the
subRoottree:- Call
calculateHashForSubtree(subRoot, false)to compute the hash forsubRoot. We do not store this hash.
- Call
-
Compare the
subRoothash with stored hashes:- Loop through the
hashStorelist and compare the hash ofsubRootwith each stored hash. - If a match is found (both hash parts are equal), return
truebecausesubRootis a subtree ofroot.
- Loop through the
-
Return
falseif no match is found:- If no matching hash is found in
hashStore, returnfalseassubRootis not a subtree ofroot.
- If no matching hash is found in
Algorithm Walkthrough
Input: root = [3, 6, 5, 1, 4], subRoot = [6, 1, 4]
-
Step 1: Initialize Constants and Data Structures:
- Initialize
MOD_PRIME_1 = 1000000007andMOD_PRIME_2 = 2147483647. - Initialize an empty list
hashStoreto store hashes of subtrees.
- Initialize
-
Step 2: Compute Hash for
root:- Start at the root node of
root(node 3). - Call
calculateHashForSubtreeon node 3:- Compute hashes for left and right subtrees of node 3.
Left Subtree of Node 3:
-
Node 3's left child is node 6.
-
Call
calculateHashForSubtreeon node 6:- Compute hashes for left and right subtrees of node 6.
Left Subtree of Node 6:
- Node 6's left child is node 1.
- Node 1 has no children, so return default hash
{3, 7}for both left and right children. - Compute the hash for node 1 using the left and right subtree hashes:
- Hash for node 1:
( (3 << 5) + (3 << 1) + 1 ) % MOD_PRIME_1 = 101,( (7 << 7) + (7 << 1) + 1 ) % MOD_PRIME_2 = 897.
- Hash for node 1:
- Store this hash
{101, 897}inhashStore.
Right Subtree of Node 6:
- Node 6's right child is node 4.
- Node 4 has no children, so return default hash
{3, 7}for both left and right children. - Compute the hash for node 4 using the left and right subtree hashes:
- Hash for node 4:
( (3 << 5) + (3 << 1) + 4 ) % MOD_PRIME_1 = 104,( (7 << 7) + (7 << 1) + 4 ) % MOD_PRIME_2 = 900.
- Hash for node 4:
- Store this hash
{104, 900}inhashStore.
-
Compute the hash for node 6 using the left and right subtree hashes (hashes of nodes 1 and 4):
- Hash for node 6:
( (101 << 5) + (104 << 1) + 6 ) % MOD_PRIME_1 = 3338,( (897 << 7) + (900 << 1) + 6 ) % MOD_PRIME_2 = 115841. - Store this hash
{3338, 115841}inhashStore.
- Hash for node 6:
Right Subtree of Node 3:
-
Node 3's right child is node 5.
-
Node 5 has no children, so return default hash
{3, 7}for both left and right children. -
Compute the hash for node 5:
- Hash for node 5:
( (3 << 5) + (3 << 1) + 5 ) % MOD_PRIME_1 = 105,( (7 << 7) + (7 << 1) + 5 ) % MOD_PRIME_2 = 901. - Store this hash
{105, 901}inhashStore.
- Hash for node 5:
-
Compute the hash for node 3 using the left and right subtree hashes (hashes of nodes 6 and 5):
- Hash for node 3:
( (3338 << 5) + (105 << 1) + 3 ) % MOD_PRIME_1 = 107899,( (115841 << 7) + (901 << 1) + 3 ) % MOD_PRIME_2 = 14826435. - Store this hash
{107899, 14826435}inhashStore.
- Hash for node 3:
- Start at the root node of
-
Step 3: Compute Hash for
subRoot:- Call
calculateHashForSubtreeonsubRoot(node 6):- The process is the same as when we computed the hash for the left subtree of node 3 in
root. - Hash for
subRoot:{3338, 115841}.
- The process is the same as when we computed the hash for the left subtree of node 3 in
- Call
-
Step 4: Compare Hashes:
- Loop through
hashStoreand check if any hash matches{3338, 115841}(the hash ofsubRoot). - A match is found in
hashStore, confirming thatsubRootis a subtree ofroot.
- Loop through
-
Step 5: Return
true:- Since a matching hash was found, return
true.
- Since a matching hash was found, return
Code
Complexity Analysis
Time Complexity
nis the number of nodes in theroottree, andmis the number of nodes insubRoot.- We traverse each node in both
rootandsubRoottrees to compute their hash values. This takesfor rootandfor subRoot. - After computing the hashes, we compare the hash of
subRootwith all stored hashes fromroot, which takes. Thus, the total time complexity is .
Space Complexity
- We store the hashes of all subtrees in
root, which requiresspace. - Additionally, the recursive depth (call stack) for the
calculateHashForSubtreefunction depends on the height of the trees, which isfor rootandfor subRoot. Therefore, the total space complexity is.
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity
An Alternate Approach Using Tree Hash
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity